Inorder successor in BST II¶
Time: O(H); Space: O(1); medium
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
The successor of a node p is the node with the smallest key greater than p.val.
You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node.
Example 1:
Input: node = {Node}
["$id":"1",
"left":["$id":"2",
"val":1,
"left":null,
"right":null,
"parent":["$ref":"1"]
],
"parent":null,
"right":["$id":"3",
"val":3,
"left":null,
"right":null,
"parent":["$ref":"1"]
],
"val":2
],
p = {Node} [1] (node.val = 1 -> node2)
Output: {Node} [2] (node.val = 2 -> node1)
Explanation:
1’s in-order successor node is 2. Note that both p and the return value is of Node type.
Example 2:
Input: node = {Node}
["$id":"1",
"left":{"$id":"2",
"left":{"$id":"3",
"left":{"$id":"4",
"left":null,
"parent":{"$ref":"3"},
"right":null,
"val":1},
"parent":{"$ref":"2"},
"right":null,
"val":2},
"parent":{"$ref":"1"},
"right":{"$id":"5",
"left":null,
"parent":{"$ref":"2"},
"right":null,
"val":4},
"val":3},
"parent":null,
"right":{"$id":"6",
"left":null,
"parent":{"$ref":"1"},
"right":null,
"val":6},
"val":5},
p = {Node} [6] (node.val = 6 -> node6)
Output: None
Explanation:
There is no in-order successor of the current node, so the answer is null.
Example 3:
Input: node = {Node}
["$id":"1",
"left":{"$id":"2",
"left":{"$id":"3",
"left":{"$id":"4",
"left":null,
"parent":{"$ref":"3"},
"right":null,
"val":2},
"parent":{"$ref":"2"},
"right":{"$id":"5",
"left":null,
"parent":{"$ref":"3"},
"right":null,
"val":4},
"val":3},
"parent":{"$ref":"1"},
"right":{"$id":"6",
"left":null,
"parent":{"$ref":"2"},
"right":{"$id":"7",
"left":{"$id":"8",
"left":null,
"parent":{"$ref":"7"},
"right":null,
"val":9},
"parent":{"$ref":"6"},
"right":null,
"val":13},
"val":7},
"val":6},
"parent":null,
"right":{"$id":"9",
"left":{"$id":"10",
"left":null,
"parent":{"$ref":"9"},
"right":null,
"val":17},
"parent":{"$ref":"1"},
"right":{"$id":"11",
"left":null,
"parent":{"$ref":"9"},
"right":null,
"val":20},
"val":18},
"val":15],
p = {Node} [15] (node.val = 15 -> node1)
Output: {Node} [17] (node.val = 17 -> node10)
Example 4:
Input: node =
["$id":"1",
"left":{"$id":"2",
"left":{"$id":"3",
"left":{"$id":"4",
"left":null,
"parent":{"$ref":"3"},
"right":null,
"val":2},
"parent":{"$ref":"2"},
"right":{"$id":"5",
"left":null,
"parent":{"$ref":"3"},
"right":null,
"val":4},
"val":3},
"parent":{"$ref":"1"},
"right":{"$id":"6",
"left":null,
"parent":{"$ref":"2"},
"right":{"$id":"7",
"left":{"$id":"8",
"left":null,
"parent":{"$ref":"7"},
"right":null,
"val":9},
"parent":{"$ref":"6"},
"right":null,
"val":13},
"val":7},
"val":6},
"parent":null,
"right":{"$id":"9",
"left":{"$id":"10",
"left":null,
"parent":{"$ref":"9"},
"right":null,
"val":17},
"parent":{"$ref":"1"},
"right":{"$id":"11",
"left":null,
"parent":{"$ref":"9"},
"right":null,
"val":20},
"val":18},
"val":15],
p = {Node} [13] (node.val = 13 -> node7)
Output: {Node} [15] (node.val = 15 -> node1)
Notes:
If the given node has no in-order successor in the tree, return null.
It’s guaranteed that the values of the tree are unique.
Remember that we are using the Node type instead of TreeNode type so their string representation are different.
Follow up:
Could you solve it without looking up any of the node’s values?
Solution¶
Successor could exist in 2 possible positions:
If node has right child, successor must be below its right child, node.right, then keep going down left.
Otherwise, successor could be node going up untill hitting first ancestor through left edge. There may be case that it keeps going up through right edge, then there is no successor.
1. Brute-Force (Value-based) [O(H), O(1)]¶
Since it is BST, we do inorder traversal. Return the node after the target node x.
But you have to use parent links to find the root first.
2. Iteration [O(H), O(1)]¶
If the node has a right child, and hence its successor is somewhere lower in the tree.
Go to the right once and then as many times to the left as you could.
Return the node you end up with.
Node has no right child, and hence its successor is somewhere upper in the tree. Go up till the node that is left child of its parent.
The answer is the parent.
[1]:
class Node(object):
def __init__(self, val, left, right, parent):
self.val = val
self.left = left
self.right = right
self.parent = parent
[2]:
class Solution2(object):
"""
Time: O(H)
Space: O(1)
"""
def inorderSuccessor(self, node):
"""
:type node: Node
:rtype: Node
"""
if not node:
return None
if node.right:
node = node.right
while node.left:
node = node.left
return node
while node.parent and node.parent.right is node:
node = node.parent
return node.parent
[4]:
s = Solution2()
node1 = Node(2, None, None, None) # id = 1, val = 2
node2 = Node(1, None,None, node1) # id = 2, val = 1
node3 = Node(3, None, None, node1) # id = 3, val = 3
node1.left = node2
node1.right = node3
res = s.inorderSuccessor(node2) # val = 2
assert res.val == 2
node1 = Node(5, None, None, None) # id = 1, val = 5
node2 = Node(3, None, None, node1) # id = 2, val = 3
node3 = Node(2, None, None, node2) # id = 3, val = 2
node4 = Node(1, None, None, node3) # id = 4, val = 1
node5 = Node(4, None, None, node2) # id = 5, val = 4
node6 = Node(6, None, None, node1) # id = 6, val = 6
node1.left = node2
node1.right = node6
node2.left = node3
node2.right = node5
node3.left = node4
res = s.inorderSuccessor(node6) # val = 6
assert res == None
node1 = Node(15, None, None, None) # id = 1, val = 15
node2 = Node(6, None, None, node1) # id = 2, val = 6
node3 = Node(3, None, None, node2) # id = 3, val = 3
node4 = Node(2, None, None, node3) # id = 4, val = 2
node5 = Node(4, None, None, node3) # id = 5, val = 4
node6 = Node(7, None, None, node2) # id = 6, val = 7
node7 = Node(13, None, None, node6) # id = 7, val = 13
node8 = Node(9, None, None, node7) # id = 8, val = 9
node9 = Node(18, None, None, node1) # id = 9, val = 18
node10 = Node(17, None, None, node9) # id = 10, val = 17
node11 = Node(20, None, None, node9) # id = 11, val = 20
node1.left = node2
node1.right = node9
node2.left = node3
node2.right = node6
node3.left = node4
node3.right = node5
node6.right = node7
node7.left = node8
node9.left = node10
node9.right = node11
res = s.inorderSuccessor(node1) # val = 15
assert res.val == 17
res = s.inorderSuccessor(node7) # val = 13
assert res.val == 15